package newBee.class1;

public class TestDemo {
    public static void main(String[] args) {
        String str = "cbacdcbc";
        String ans = smallestSubsequence(str);
        System.out.println("ans = " + ans);
    }

    /**
     * cnts[t]：判断后面是否还有该字符
     */
    public static String smallestSubsequence(String str) {
        int r = 0, max = 26;
        char[] chars = str.toCharArray();
        int[] stack = new int[max], cnts = new int[max]; // 字符词频表
        boolean[] enStack = new boolean[max]; // 字符入栈标识

        for (char c : chars) cnts[c - 'a']++; // 统计字符词频

        for (char c : chars) {
            if (!enStack[c - 'a']) {
                while (r > 0 && stack[r - 1] > c && cnts[stack[r - 1]  - 'a'] > 0) {
                    enStack[stack[r - 1] - 'a'] = false;
                    r--;
                }
                stack[r++] = c;
                enStack[stack[r - 1]  - 'a'] = true;
            }
            cnts[c - 'a']--;
        }
        return new String(stack, 0, r);
    }


}
